package Q1728

import java.util.*
import kotlin.collections.ArrayDeque
import kotlin.collections.List
import kotlin.collections.MutableList


/**
 * 猫和老鼠 hard
 * @author 23737
 * @date 2022.5.10
 */
class Main {

}

fun main(){

}

 class Solution {
    var dirs = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
    var rows = 0
    var cols = 0
    lateinit var grid: Array<String>
    var catJump = 0
    var mouseJump = 0
    var food = 0
    lateinit var degrees: Array<Array<IntArray>>
    lateinit var results: Array<Array<Array<IntArray>>>
    fun canMouseWin(grid: Array<String>, catJump: Int, mouseJump: Int): Boolean {
        rows = grid.size
        cols = grid[0].length
        this.grid = grid
        this.catJump = catJump
        this.mouseJump = mouseJump
        var startMouse = -1
        var startCat = -1
        for (i in 0 until rows) {
            for (j in 0 until cols) {
                val c = grid[i][j]
                if (c == 'M') {
                    startMouse = getPos(i, j)
                } else if (c == 'C') {
                    startCat = getPos(i, j)
                } else if (c == 'F') {
                    food = getPos(i, j)
                }
            }
        }
        val total = rows * cols
        degrees = Array(total) { Array(total) { IntArray(2) } }
        results = Array(total) {
            Array(total) {
                Array(2) {
                    IntArray(2)
                }
            }
        }
        val queue: Queue<IntArray> = LinkedList<IntArray>()
        // 计算每个状态的度
        for (mouse in 0 until total) {
            val mouseRow = mouse / cols
            val mouseCol = mouse % cols
            if (grid[mouseRow][mouseCol] == '#') {
                continue
            }
            for (cat in 0 until total) {
                val catRow = cat / cols
                val catCol = cat % cols
                if (grid[catRow][catCol] == '#') {
                    continue
                }
                degrees[mouse][cat][MOUSE_TURN]++
                degrees[mouse][cat][CAT_TURN]++
                for (dir in dirs) {
                    run {
                        var row = mouseRow + dir[0]
                        var col = mouseCol + dir[1]
                        var jump = 1
                        while (row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#' && jump <= mouseJump
                        ) {
                            val nextMouse = getPos(row, col)
                            val nextCat = getPos(catRow, catCol)
                            degrees[nextMouse][nextCat][MOUSE_TURN]++
                            row += dir[0]
                            col += dir[1]
                            jump++
                        }
                    }
                    var row = catRow + dir[0]
                    var col = catCol + dir[1]
                    var jump = 1
                    while (row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#' && jump <= catJump) {
                        val nextMouse = getPos(mouseRow, mouseCol)
                        val nextCat = getPos(row, col)
                        degrees[nextMouse][nextCat][CAT_TURN]++
                        row += dir[0]
                        col += dir[1]
                        jump++
                    }
                }
            }
        }
        // 猫和老鼠在同一个单元格，猫获胜
        for (pos in 0 until total) {
            val row = pos / cols
            val col = pos % cols
            if (grid[row][col] == '#') {
                continue
            }
            results[pos][pos][MOUSE_TURN][0] = CAT_WIN
            results[pos][pos][MOUSE_TURN][1] = 0
            results[pos][pos][CAT_TURN][0] = CAT_WIN
            results[pos][pos][CAT_TURN][1] = 0
            queue.offer(intArrayOf(pos, pos, MOUSE_TURN))
            queue.offer(intArrayOf(pos, pos, CAT_TURN))
        }
        // 猫和食物在同一个单元格，猫获胜
        for (mouse in 0 until total) {
            val mouseRow = mouse / cols
            val mouseCol = mouse % cols
            if (grid[mouseRow][mouseCol] == '#' || mouse == food) {
                continue
            }
            results[mouse][food][MOUSE_TURN][0] = CAT_WIN
            results[mouse][food][MOUSE_TURN][1] = 0
            results[mouse][food][CAT_TURN][0] = CAT_WIN
            results[mouse][food][CAT_TURN][1] = 0
            queue.offer(intArrayOf(mouse, food, MOUSE_TURN))
            queue.offer(intArrayOf(mouse, food, CAT_TURN))
        }
        // 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜
        for (cat in 0 until total) {
            val catRow = cat / cols
            val catCol = cat % cols
            if (grid[catRow][catCol] == '#' || cat == food) {
                continue
            }
            results[food][cat][MOUSE_TURN][0] = MOUSE_WIN
            results[food][cat][MOUSE_TURN][1] = 0
            results[food][cat][CAT_TURN][0] = MOUSE_WIN
            results[food][cat][CAT_TURN][1] = 0
            queue.offer(intArrayOf(food, cat, MOUSE_TURN))
            queue.offer(intArrayOf(food, cat, CAT_TURN))
        }
        // 拓扑排序
        while (!queue.isEmpty()) {
            val state = queue.poll()
            val mouse = state[0]
            val cat = state[1]
            val turn = state[2]
            val result = results[mouse][cat][turn][0]
            val moves = results[mouse][cat][turn][1]
            val prevStates = getPrevStates(mouse, cat, turn)
            for (prevState in prevStates) {
                val prevMouse = prevState[0]
                val prevCat = prevState[1]
                val prevTurn = prevState[2]
                if (results[prevMouse][prevCat][prevTurn][0] == UNKNOWN) {
                    val canWin =
                        result == MOUSE_WIN && prevTurn == MOUSE_TURN || result == CAT_WIN && prevTurn == CAT_TURN
                    if (canWin) {
                        results[prevMouse][prevCat][prevTurn][0] = result
                        results[prevMouse][prevCat][prevTurn][1] = moves + 1
                        queue.offer(intArrayOf(prevMouse, prevCat, prevTurn))
                    } else {
                        degrees[prevMouse][prevCat][prevTurn]--
                        if (degrees[prevMouse][prevCat][prevTurn] == 0) {
                            val loseResult = if (prevTurn == MOUSE_TURN) CAT_WIN else MOUSE_WIN
                            results[prevMouse][prevCat][prevTurn][0] = loseResult
                            results[prevMouse][prevCat][prevTurn][1] = moves + 1
                            queue.offer(intArrayOf(prevMouse, prevCat, prevTurn))
                        }
                    }
                }
            }
        }
        return results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN && results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES
    }

    fun getPrevStates(mouse: Int, cat: Int, turn: Int): List<IntArray> {
        val prevStates: MutableList<IntArray> = ArrayList()
        val mouseRow = mouse / cols
        val mouseCol = mouse % cols
        val catRow = cat / cols
        val catCol = cat % cols
        val prevTurn = if (turn == MOUSE_TURN) CAT_TURN else MOUSE_TURN
        val maxJump = if (prevTurn == MOUSE_TURN) mouseJump else catJump
        val startRow = if (prevTurn == MOUSE_TURN) mouseRow else catRow
        val startCol = if (prevTurn == MOUSE_TURN) mouseCol else catCol
        prevStates.add(intArrayOf(mouse, cat, prevTurn))
        for (dir in dirs) {
            var i = startRow + dir[0]
            var j = startCol + dir[1]
            var jump = 1
            while (i >= 0 && i < rows && j >= 0 && j < cols && grid[i][j] != '#' && jump <= maxJump) {
                val prevMouseRow = if (prevTurn == MOUSE_TURN) i else mouseRow
                val prevMouseCol = if (prevTurn == MOUSE_TURN) j else mouseCol
                val prevCatRow = if (prevTurn == MOUSE_TURN) catRow else i
                val prevCatCol = if (prevTurn == MOUSE_TURN) catCol else j
                val prevMouse = getPos(prevMouseRow, prevMouseCol)
                val prevCat = getPos(prevCatRow, prevCatCol)
                prevStates.add(intArrayOf(prevMouse, prevCat, prevTurn))
                i += dir[0]
                j += dir[1]
                jump++
            }
        }
        return prevStates
    }

    fun getPos(row: Int, col: Int): Int {
        return row * cols + col
    }

    companion object {
        const val MOUSE_TURN = 0
        const val CAT_TURN = 1
        const val UNKNOWN = 0
        const val MOUSE_WIN = 1
        const val CAT_WIN = 2
        const val MAX_MOVES = 1000
    }
}
